package 迷宫问题;

public class 迷宫问题 {

	public static void main(String[] args) {
		/*
			1. 使用数组代表地图
			2. 数字 0 表示未走过，可以走的路
			3. 数字 1 表示墙
			4. 数字 2 表示走过的路
			5. 数字 3 表示此路不通，死路
			6. 迷宫策略 先向右，再向下，再向左，再向上
		 */
		//二维数组表示地图
		int[][] map = new int[8][7];
		//设置墙，1 表示
		for(int i = 0; i < 7 ; i++) {
			map[0][i] = 1;
			map[7][i] = 1;
		}
		for(int i = 0; i < 8; i++) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		//设置挡板
		map[3][1] = 1;
		map[3][2] = 1;
		//输出地图
		for(int i = 0 ; i < map.length ; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		/*
			1 1 1 1 1 1 1 
			1 0 0 0 0 0 1 
			1 0 0 0 0 0 1 
			1 1 1 0 0 0 1 
			1 0 0 0 0 0 1 
			1 0 0 0 0 0 1 
			1 0 0 0 0 0 1 
			1 1 1 1 1 1 1 
		*/
		
		//调用找路方法
		boolean f = findWay(map , 1 , 1);
		System.out.println(f);
		//查看地图
		/*
			1 1 1 1 1 1 1 
			1 2 2 2 2 2 1 
			1 0 0 0 0 2 1 
			1 1 1 0 0 2 1 
			1 0 0 0 0 2 1 
			1 0 0 0 0 2 1 
			1 0 0 0 0 2 1 
			1 1 1 1 1 1 1 
		 */
		//输出地图
		for(int i = 0 ; i < map.length ; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		
	}

	/**
	 * 
	 * @param map 地图
	 * @param i 开始位置
	 * @param j
	 * @return
	 */
	private static boolean findWay(int[][] map, int i, int j) {
		
		//先判断出口是否为 2 ，2 表示已经到达出口
		if(map[6][5] == 2) {
			return true;
		}else {
			//表示没走过
			if(map[i][j] == 0) {
				//假设走这个路
				map[i][j] = 2;
				//先走右边,进入方法，如果最后走通了，返回true，否则，else走下边
				if(findWay(map, i, j+1)) {
					return true;
				}else if(findWay(map, i+1, j)) {//走下边
					return true;
				}else if(findWay(map, i-1, j)) {//走左边
					return true;
				}else if(findWay(map, i, j-1)) {//走上边
					return true;
				}else {
					//走不通
					map[i][j] = 3;
					return false;
				}
				
			}else {//不是 0 ，就是 1 2 3，也不能走
				return false;
			}
		}
		
	}
}
